#ifndef A_H
#define A_H
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;
struct node
{
    /* data */
    int data;
    struct node *next;
};

struct ListNode
{
    int val;
    ListNode *next;
    //初始化支持 ListNode(x) 方式，即 把x赋给val，next赋值NULL。
    ListNode(int x) : val(x), next(NULL) {}
};

class A
{
public:
    void Say();

    //<l1>two sum
    void L1TwoSum();

    //L1
    std::vector<int> TwoSum(std::vector<int> &nums, int target);

    //L2
    void L2LinkSum();
};

class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *prenode = new ListNode(0);
        ListNode *lastnode = prenode;

        int val = 0;
        while (val || l1 || l2)
        {
            val = val + (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
            lastnode->next = new ListNode(val % 10);
            lastnode = lastnode->next;
            val = val / 10;
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
        }

        ListNode *res = prenode->next;
        delete prenode;
        return res;
    }
};

//求出最大回文串-Manacher算法
class Solution5
{
public:
    string longestPalindrome(string s)
    {
        std::string t = "$#"; //插入“#”
        for (auto c : s)
        {
            t += c;
            t += '#';
        }
        vector<int> p(t.size(), 0);

        //mx 表示某个回文串延伸在最右端半径的下标
        //id 表示这个回文串最中间位置的下标
        //resLen 表示对应在s中的最大子回文串的半径
        //resCenter表示最大子回文串的中间位置

        int mx = 0, id = 0, resLen = 0, resCenter = 0;

        //建立p数组
        for (int i = 1; i < t.size(); i++)
        {
            //更新p[i]的值
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;

            //遇到三种特殊情况，需要利用中心拓展法
            while (t[i + p[i]] == t[i - p[i]])
                p[i]++;

            //半径瞎掰哦i+p[i]超过边界mx，需要更新
            if (mx < i + p[i])
            {
                mx = i + p[i];
                id = i;
            }
            //更新最大回文子串的信息
            if (resLen < p[i])
            {
                resLen = p[i];
                resCenter = i;
            }
        }
        //最长回文子串长度为半径-1，起始位置为中间位置减去半径除以2
        return s.substr((resCenter - resLen) / 2, resLen - 1);
    }
};

//Z型
class Solution6
{
public:
    string convert(string s, int numberRows)
    {
        if (numberRows == 1)
            return s;
        vector<string> rows(min(numberRows, int(s.size())));
        int curRow = 0;
        bool goingDown = false;

        for (char c : s)
        {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numberRows - 1)
                goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }
        string ret;
        for (string row : rows)
            ret += row;

        std::cout << ret << std::endl;
        return ret;
    }
};

//from 321 to 123
class Solution7
{
public:
    int reveres(int x)
    {
        int result = 0;
        string si = to_string(x);
        int ns = si.length() - 1;
        int sri = 0;
        char sr[ns];
        for (int n = ns; n > -1; n--)
        {
            sr[sri] = si[n];
            sri++;
        }

        // cout<<sr<<endl;
        result = atoi(sr);

        return result;
    }
};

// [−2^31, 2^31 − 1]， 即：[-2147483648, 2147483647]
class Solution7_1
{
public:
    int reverse(int x)
    {
        int rev = 0;
        while (x != 0)
        {
            int pop = x % 10;
            x /= 10;
            if (rev > INT32_MAX / 10 || (rev == INT32_MAX / 10 && pop > 7))
                return 0;
            if (rev < INT32_MIN / 10 || (rev == INT32_MIN / 10 && pop < -8))
                return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

//使用c++标准字符串IO库<sstream>
class Solution8
{
public:
    int myAtoi(string str)
    {
        int digit = 0;
        istringstream is(str);
        is >> digit;
        return digit;
    }
};

#include <algorithm>
class Solution9
{
public:
    void TestIsPlindrome()
    {
        int x=1122221;
       if(isPalindrome(x))
       {
           cout<<"Is palindrome"<<endl;
       }
       else
       {
           cout<<"not"<<endl;
       }
       
    }

    bool isPalindrome(int x)
    {
        string tmp = to_string(x);
        string tmp2=tmp;
        reverse(tmp2.begin(),tmp2.end());
        if(tmp==tmp2)
        {
            return true;
        }
        else
        {
            /* code */
            return false;
        }
    }
};

class Solution10
{
public: 
    bool isMatch(string s,string p)
    {
        
    }
};

#endif
